package org.lyc.lanqiao.bank;

import java.util.Scanner;

/**
 * 分考场 (图着色问题)
 * https://www.lanqiao.cn/problems/109/learning/?page=1&first_category_id=1&second_category_id=3&difficulty=30
 *
 * @author Liu Yicong
 * @date 2024/3/9
 */
public class JAllocExamRoom {
	static final int N = 110;
	static int[][] graph = new int[N][N];//关系表
	static int[][] p = new int[N][N];//房间状态
	static int num = N;//考场数量
	static int n, m;

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		m = scan.nextInt();
		for (int i = 1; i <= m; i++) {
			int u = scan.nextInt();
			int v = scan.nextInt();
			graph[u][v] = graph[v][u] = 1;
		}
		p[1][0] = 1;
		dfs(1, 1);
		System.out.println(num);
		scan.close();
	}

	private static void dfs(int curr, int used_color_cnt) {
		if (used_color_cnt >= num) {
			return;
		}
		if (curr == n) {
			num = used_color_cnt;
			return;
		}

		int j, k;
		for (j = 1; j <= used_color_cnt; j++) {
			k = 0;
			while (p[j][k] != 0 && graph[curr + 1][p[j][k]] == 0) k++;//为第x+1个学生找空教室
			if (p[j][k] == 0) {
				//有空教室
				p[j][k] = curr + 1;
				dfs(curr + 1, used_color_cnt);
				p[j][k] = 0;
			}
		}
		// 开辟一个新的教室
		p[j][0] = curr + 1;
		dfs(curr + 1, used_color_cnt + 1);
		p[j][0] = 0;
	}

}
